1. Field of the Invention
This invention relates to apparatus for generating two dimensional representations of three dimensional objects, particularly for generating animated displays corresponding to object motion in three dimensions, and to methods of generating such images.
2. Description of the Related Arts
Three dimensional graphics processing apparatus is used in a number of applications; for instance, in generating displays of the appearance of an object from several angles during computer aided design and computer aided manufacture, or in electronic video arcade games, or in flight simulators for training. Other applications include visualising mathematical surfaces, or plotting data of any kind.
To provide animation, it is necessary to update the image at rates approaching 25 or 30 frames per second, so that a human eye sees a continuous change rather than a series of static images (although lower speeds, for example 10 frames per second, may be acceptable in some applications). The speed at which the processing apparatus can perform calculations, coupled with the minimum acceptable frame rate, provides a limit to the number of calculations which can be performed to generate each image. In three dimensional graphics, it is necessary in each image to calculate the projection of the three dimensional objects concerned into two dimensions, and depending upon the complexity of the object, this can involve a considerable number of calculations.
In some applications, a relatively low resolution model of a three dimensional object is acceptable. For example, in computer aided design (CAD), data defining a three dimensional object is retained by the processor as coordinates of a plurality of points on the object surface which are displayed as a "wire frame" image. When the object is to be displayed as moving in three dimensions, the processor calculates, at the necessary frame repetition rate, the projection of the points into two dimensions and draws a display in which the points are connected on a screen; the relatively small number of points in the wire frame model makes this possible. Since real time calculation of the two dimensional projections is thus possible, the processor can provide input means and control means enabling a human operator to directly manipulate the movement of the viewpoint relative to the object, for example to see it from a different angle.
On the other hand, animated sequences showing the movement of three dimensional objects which are used in films, for example, are required to exhibit much finer resolution, not only spatially but also in grey scale and colour. Providing animated representations which are indistinguishable from photographs ("photorealism") is an object of much present research, but at present, although such quality is attainable, it cannot be achieved in real time and consequently cannot provide for interactive manipulation by an operator. Instead, images are calculated one by one, stored, and then displayed.
Currently, image synthesis is often performed by synthesising an image as a number of polygons defined by corner points, and then processing each polygon in turn to define, for each pixel of the polygon, the pixel colour in accordance with predetermined colour and transparency parameters associated with the polygon. The process of creating and colouring pixels of the polygon is generally referred to as "rendering". Whereas the operations of defining the positions of the corners of the polygon require relatively complex mathematical operations on a relatively small number of points, the task of rendering involves relatively simple multiplications and additions repetitively performed on a very large number of pixels. Accordingly, dedicated image processing apparatus is known which accepts data defining the corners of the polygon and rendering parameters, and writes corresponding pixel data into an image buffer for display. However, such apparatus is at present expensive.
A particular problem which occurs with three dimensional graphics is that of hidden line or hidden surface removal. It is desired, when displaying solid objects, that nearer parts of the object obscure further parts. A common approach is to test, when a given pixel is rendered, whether it lies in front (and therefore occludes) or behind, (and therefore is occluded by) the pixel (if any) which is already within the image buffer. Accordingly, each pixel needs to be assigned a depth value. This technique is referred to as the "z-buffer algorithm". Although it is simple, it necessarily involves a large number of comparison operations (on the order of the number of pixels in the image buffer), and thus requires very fast image processing hardware for real time operation.
An alternative technique is to perform the decision as to whether a part of the image occludes, or is occluded by another, at the polygon level prior to rendering. Accordingly, in this technique, the processor considers polygons and decides which lies in front of the other in the view which is to be drawn. The number of decisions to be made is reduced from one per pixel to one per polygon, but the computation complexity of each decision is considerably increased, which slows the process.
The "Painter's Algorithm" for Hidden Surface Removal examines the coordinates of the vertices of the polygons, and ranks the polygons into order of decreasing distance from the display plane (viewpoint). The polygons are then rendered in order of distance, so that the pixels of the most distant polygons are first written into the image buffer, and are overwritten as necessary by those of nearer polygons. However, this technique requires the sorting operation of all polygons to be performed for each new image to be displayed (or, at least, each time the image changes) and consequently requires a large amount of computation in real time.
In a known technique, polygons are viewed as having two faces; one face directed inwardly towards the interior of the object (the "behind" face) and one face directed outwardly of the object (the "front" face). For a solid object, the "behind" face of a polygon is never visible; only polygons which face forwards therefore need to be displayed. Accordingly, a decision is made prior to rendering whether, from the viewing angle concerned, a given polygon is showing its front (outer) or behind (inner) face, and only those polygons which are facing forward are rendered. This reduces the problem of hidden surface removal, but does not eliminate the problem altogether.
A further known technique is known as "binary partitioning" (BSP), described in "On visible surface generation by a priori tree structures" Kedem et al, Computer Graphics Vol 14, No. 3 (1980) pp 124-133 and "Near real time shaded display of rigid objects", Abram et al, Computer Graphics Vol 17, No. 3 (1983) pp 65-72. In this technique, prior to animation, a preprocessing stage is performed in which a tree structured model is built in memory, each node in the tree being a polygon and pointing to successor and predecessor nodes (if any).
The function of the tree is that all successor (for example) nodes to a polygon will be polygons which, from the first polygon's point of view, lie wholly in front of that polygon and all predecessor (say) nodes are likewise wholly behind that polygon. To construct such a tree it is thus necessary that no polygon should cross the plane of any other, or otherwise there would be an indeterminacy as to whether it lay in front or behind that polygon. Each polygon may therefore be thought of as dividing space into two; a space in front of the plane and a space behind the plane, hence the name of the technique.
When it is desired to draw the object, the root polygon is initially selected. To determine which way through the tree to progress, the plane equation of the polygon Ax+By+Cz+D is solved using the coordinates of the viewing position from which the three dimensional object is to be drawn; the sign of the result determines whether the viewing position lies in front or behind the polygon (ie whether the polygon is facing towards or away from the viewing position). In dependence upon this sign, it is determined whether it is the successor nodes or the predecessor nodes of the tree which are to correspond to polygons lying behind others; in other words, the direction in which the tree is to be traversed.
A next polygon lying behind the root polygon is then selected, and the above process is repeated. When a polygon having none behind it is reached, that polygon is drawn, and the next forward polygon is again selected. If that polygon now has none behind it, it is drawn; otherwise the next polygon behind it is selected. Thus, every polygon behind a given polygon is drawn before that polygon, and then it is drawn.
However, in many cases polygons do not lie wholly behind others; such polygons are therefore split in two parts, one lying in front and one behind. This leads to a substantial increase in the number of polygons. Further, the performance of the technique depends upon the polygon chosen as the root of the tree while it is constructed and appropriate selection criteria are not known. Further, a plane equation must be solved for each polygon during traversal of the tree, for each frame to be displayed, which is computationally expensive and slow.